package 剑指offer_专项突击版.简单;

/**
 * 给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
 * <p>
 * 输入为 非空 字符串且只包含数字 1 和 0。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: a = "11", b = "10"
 * 输出: "101"
 * 示例 2:
 * <p>
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/JFETK5
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/10/27 9:51
 */
public class _002_二进制加法 {

    public static void main(String[] args) {
        _002_二进制加法 a = new _002_二进制加法();
        System.out.println(a.addBinary("110010", "100"));
    }
    
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        // 二进制数区分长短
        String c = a.length() >= b.length() ? a : b;
        String d = a.length() < b.length() ? a : b;

        // 定义保存进位数
        int carry = 0;
        // 从右到左遍历短的进制数
        for (int i = 0; i < d.length(); i++) {
            int dIndex = d.length() - i - 1;
            int cIndex = c.length() - i - 1;
            // 计算两个进制数和进位数相加后的最终结果
            carry = (c.charAt(cIndex) - '0' + d.charAt(dIndex) - '0') + carry;
            // %2后进行拼接
            sb.append(carry % 2);
            // 维护进位数
            carry /= 2;
        }
        // 短的遍历完后继续遍历长的
        for (int i = d.length(); i < c.length(); i++) {
            int index = c.length() - i - 1;
            carry = (c.charAt(index) - '0') + carry;
            sb.append(carry % 2);
            carry /= 2;
        }
        // 如果还有进位则继续进行拼接
        while(carry > 0) {
            sb.append(carry % 2);
            carry /= 2;
        }
        // 结果反转返回
        return sb.reverse().toString();
    }

}
